Fault propagation path inference techniques are used to infer a path along which a fault that satisfies an output pattern inclusive of a faulty output may possibly propagate. For example, such art can be used as part of a system for inferring a faulty location in a sequential circuit, as described in the specification of Japanese Patent Kokai Publication JP-A-8-146093 (U.S. Pat. No. 2,655,105) or Japanese Patent Kokai Publication JP-A-10-62494 (U.S. Pat. No. 2,921,502). The fault may exist in a combinational circuit or the fault state may be included in an input pattern.
An reverse logic expansion system that makes use of backtracking in which Don't Care has been introduced can be utilized as a system for inferring a fault propagation path in the prior art [see the specification of Japanese Patent Kokai Publication JP-A-10-154171 (U.S. Pat. No. 2956624)]. This system extracts a fault propagation path by comparing an input inferred state, which has been found by reverse logical inference, and the logic state obtained in a combinational logic circuit in the process of making the reverse logic expansion, with an expected value obtained in advance by a logic simulation in a normal circuit. In accordance with the method set forth in the specification of Japanese Patent Kokai Publication JP-A-10-154171 (U.S. Pat. No. 2,956,624), it is possible to obtain all input logic states that satisfy output logic states. By making the comparison with the expected value obtained by the logic simulation, it is possible to extract the fault propagation path.
However, a very large number of decisions are made in multiplier circuits and the like and computation time is prolonged significantly.
Accordingly, the specification of Japanese Patent Kokai Publication JP-A-11-153646 proposes a fault propagation path extraction system for speeding up processing by limiting decisions of logic values regarding signal lines to signal lines that are related to a fault propagation path.
The structure of fault propagation path extraction system proposed by the specification of Japanese Patent Kokai Publication JP-A-11-153646 will be described with reference to FIG. 16. This conventional fault propagation path extraction system includes an input unit 1 such as a keyboard, a data processing unit 2 operated under the control of a program, a storage unit 4 such as a hard disk or memory for storing information, and an output unit 5 such as a display unit or printer.
The storage unit 4 has a logic-circuit structure memory 41, a logic contradiction memory 42, a decision state memory 43 and a logic state memory 44.
Previously stored in the logic-circuit structure memory 41 is the constitution of a logic circuit, such as type of gates, connection relationship between gates, connection relationship between gates and signal lines, and connection relationship between signal lines.
The logic contradiction memory 42 stores the gates in which logic contradictions have occurred during implication processing and the number of times logic contradictions have occurred.
The decision state memory 43 stores a decision level representing how many times decisions have been rendered and a decision level at the time when the logic state of each signal line is inferred by implication.
The logic state memory 44 stores the logic state of each signal line undergoing processing, the implication history and the logic state (expected value) of each signal line when a circuit is normal.
The data processing unit 2 has initialization means 21, implication means 22, logic contradiction discrimination means 23, processing-end discrimination means 24, backtrack means 25, undetermined-gate retrieval means 26, retrieval means 27 for retrieving a line influenced by a fault propagation path, logic value decision means 29, logic value comparison means 31 and extraction means 32 for extracting a line related to a fault output terminal.
The initialization means 21 sets the logic-circuit type provided by the input unit 1 and the logic state of an input/output terminal and initializes the logic state of a signal line. The initialization means 21 further initializes the decision level and sets an upper-limit value.
The implication means 22 refers to a logic circuit structure that has been stored in the logic-circuit structure memory 41 and to the logic state of each signal line that has been stored in the logic state memory 44, performs an implication operation in a gate connected to an input/output signal line set by the initialization means 21 and in a gate connected to a signal line decided by the logic value decision means 29, and infers the logic states of input/output signal lines of the gates.
In case where a logic value is inferred anew, the implication means 22 records the logic value and a history of implications in the logic state memory 44 and records a decision level, which indicates under how many decisions the inference was made, in the decision state memory 43.
If a logic contradiction occurs during an implication operation, the implication means 22 refers to the logic contradiction memory 42 and determines whether the number of logic contradictions has exceeded a predetermined allowable number. If the number of logic contradictions is greater than the allowable number, then, in order to improve the inference precision of logic states in the circuit, the implication means 22 may execute processing such as referring to the history of implications stored in the logic-circuit structure memory 41, the logic contradiction memory 42 and logic state memory 44, initializing the logic state of the signal line that is the cause of the logic contradiction and updating the information in the logic contradiction memory 42, decision state memory 43 and logic state memory 44.
The logic contradiction discrimination means 23 refers to the logic contradiction memory 42 and determines whether the number of logic contradictions on a signal line detected by the implication means 22 has exceeded a predetermined allowable number.
The processing-end discrimination means 24 refers to the logic state of each signal line stored in the logic state memory 44 and determines whether the logic states of all signal lines have been inferred.
The backtrack means 25 refers to the state of the decision stored in the decision state memory 43 and to the logic state of a signal line stored in the logic state memory 44, erases the logic state of a decision level for which processing has been completed as well as the history of implications and logic contradictions and returns the logic state of each signal line back to the logic state that prevailed prior to the rendering of the decision.
The undetermined-gate retrieval means 26 examines the logic states of the input/outputs of the gates in the combinational circuit and retrieves gates the logic state of which is incomplete. For example, if the output signal in a NAND gate is “1”, one of the input signals is always “0”. However, when the logic states of the input signal lines have not been decided and which signal line is “0” is unknown, then the input/output logic state of this gate is incomplete and the gate is an undetermined gate.
The retrieval means 27 that retrieves a line influenced by a fault propagation path refers to the logic circuit structure stored in the logic-circuit structure memory 41 and logic state of each signal line stored in the logic state memory 44 and retrieves an undetermined gate having an output signal for which the fault state has been inferred. This gate is retrieved from undetermined gates that have been retrieved by the undetermined-gate retrieval means 26.
The logic value decision means 29 selects an input signal line of an undetermined gate for which the output signal is faulty, this gate having been detected by the retrieval means 27 that retrieves a line influenced by a fault propagation path, and decides the logic state.
The logic value comparison means 31 compares the obtained logic state of each signal line with an expected value representing the logic state of each signal line found by logic simulation in a normal circuit, and extracts the fault propagation path.
The extraction means 32 extracts, from the fault propagation paths that have been extracted by the logic value comparison means 31, a fault propagation path that will have a direct influence upon a fault output terminal when a fault exists on the path, and outputs data to the output unit 5.
FIG. 17 is a flowchart useful in describing the operation of the fault propagation path extraction system as defined in the prior art. The operation of this system will be described with reference to FIGS. 16, 17 and 18.
The logic state of an input/output terminal provided by the input unit 1 is set in the initialization means 21 to initialize a decision level (dlevel) that represents the number of times a decision is rendered (steps A1 and A2 in FIG. 17).
Next, the implication means 22 performs an implication operation (step A4). The implication is an operation for inferring, from the already inferred logic state of an input/output line of a gate at each gate, the logic state of an input/output line of a gate for which an inference has not yet been made. The implication means 22 retrieves a gate for which an implication operation is possible. Namely, using the function of the gate and the logic state of an input/output line connected to this gate and for which the logic state has been determined, the implication means 22 retrieves a gate for which it is possible to imply the logic state of an input/output line that is connected to the above-mentioned gate and whose logic state has not yet been decided.
The logic state of the input/output signal line at the detected gate is then inferred. The inferred logic state is recorded in the logic-circuit structure memory 41 and is recorded also in the decision state memory 43 together with the decision level at this time and the history of the implication operation.
FIGS. 7a and 7b illustrate a specific example of an implication operation in a two-input NAND gate, in which FIG. 7a shows the result of logic state inference applied to an output signal line in an instance where the logic states of input signal lines of the two-input NAND gate have been decided, and FIG. 7b shows the result of logic state inference applied to the input signal lines in an instance where the logic state of the output signal line of the two-input NAND gate has been decided. In the case of the NAND gate shown in FIG. 7a, it is inferred that the logic state of the output signal line will be “1” if the logic state of even one of the input signal lines is “0”, and it is inferred that the logic state of the output signal line will be “0” if the logic states of all input signal lines are “1”s. If the logic state of the output signal line of the two-input NAND gate is “0”, as shown in FIG. 7b, it is inferred that the logic states of the input signal lines are all “1”s. If the logic state of the output signal line of the two-input NAND gate is “1” and the logic state of one of the input signal lines is “1”, then it is inferred that the logic state of the other input signal line is “0”.
The logic contradiction discrimination means 23 refers to the logic contradiction memory 42 to determine whether the number of logic contradictions has exceeded an allowable number (step A5 in FIG. 17).
If the logic contradiction discrimination means 23 finds that the number of contradictions is not greater than the allowable number (“NO” at step A5), then the processing-end discrimination means 24 refers to the signal-line logic states that have been stored in the logic state memory 44 and determines whether the logic states of all signal lines have been inferred to be “0”, “1” or “X” (step A6). If the number of contradictions is greater than the allowable number (“YES” at step A5), this means that a fault propagation path will not be found by the present decision and, hence, control proceeds to the processing of step A14.
If it is determined that the inferring of the logic states of all signals lines is not finished (“NO” at step A6), then the undetermined-gate retrieval means 26 examines the input/output logic states of the gates in the combinational circuit and retrieves undetermined gates for which the logic state is incomplete (step A7).
Next, the retrieval means 27 for retrieving a line influenced by a fault propagation path refers to the logic circuit structure stored in the logic-circuit structure memory 41 and logic state of each signal line stored in the logic state memory 44 and retrieves an undetermined gate having an output signal for which the fault state has been inferred (step A8). The retrieval is made from undetermined gates retrieved at step A6.
The logic value decision means 29 renders a “0” decision with respect to a detected signal line and increments the decision level (dlevel) that represents the number of times a decision has been rendered (step A10). Control then returns to implication processing (step A4) by the implication means 22.
If the processing-end discrimination means 24 determines at step A6 that the logic states of all signal lines have been inferred (“YES” at step A6), this means that a logic state in the circuit is “0”, “1” or “X”. Accordingly, the logic value comparison means 31 extracts a signal line whose state is different from that of the expected value, i.e., extracts a fault propagation path (step A12). Furthermore, the extraction means 32 extracts from the fault propagation paths a fault propagation path that will have a direct influence upon a fault output terminal when a fault exists on the path, and outputs this data to the output unit 5 (step A13).
Next, it is determined whether decision processing for both “0” and “1” has been completed with regard to all lines for which decisions have been rendered (step A14). If it is found at step A14 that the logic states of all signal lines have been inferred, then the logic states of signal lines in the combinational logic circuit will have been inferred to be “0”, “1” or “X”. The processing of step A14 is executed also in a case where a contradiction has been detected by the logic contradiction discrimination means 23.
If the processing-end discrimination means 24 determines that decision processing has not ended (“NO” at step A14), the backtrack means 25 retrieves one decision line, the state of which has not been decided to be “1”, from lines having a high decision level, initializes the logic state of a signal line inferred in a decision whose level is higher than that of the decision of the detected decision line and returns the logic state of each signal line to the logic state that prevailed prior to the rendering of this decision (step A15). The logic value decision means 29 decides that the state of the decision line detected by the backtrack means 25 is “1” (step A16), after which control returns to the implication operation (step A4) by the implication means 22.
If the processing-end discrimination means 24 determines that decision processing has ended (“YES” at step A14), then processing for extracting a fault propagation path is exited.
The conventional system for extracting a fault propagation path will be described in detail with reference to FIGS. 16, 17, 8 and 18. A case where this art is applied to a combinational circuit shown in FIG. 8 will be described as a specific example.
Consider a case where the expected values of input/output terminals of gates of interest and the logic values (L22=1, L23=1) of output signals are given as the initial state. Accordingly, L23 is the fault output.
First, the initialization means 21 sets the logic states and expected values of the input/output terminals and signal lines. The initialization means 21 sets the following: L1=X[1], L2=X[1], L3=X[1], L6=X[1], L7=X[1], L22=1[1], L23=1[0]. The numerals enclosed by the brackets represent the expected values.
The initialization means 21 initializes the decision level (dlevel) (step A2 in FIG. 17) and then the implication means 22 finds the logic values of signal lines in the logic circuit at step A4. Here there is no signal line implicated by L22=1, L23=1. Since a logic contradiction does not occur, the logic contradiction discrimination means 23 determines that there is no logic contradiction (“NO” at step A5).
Since a fault propagation path that will cause a fault output at L23 is not found, the processing-end discrimination means 24 determines that processing is not finished (“NO” at step A6) and control proceeds to step A7.
NAND gates G22, G23, for which the output signals are “1” and for which the input signals have not yet been inferred as being “0”, are retrieved as undetermined gates by the undetermined-gate retrieval means 26 at step A7.
At step A8 the retrieval means 27 for retrieving a line influenced by a fault propagation path selects L16 as a signal line for which a logic value has not been determined. The selection is made from the input signal lines of gate G23 having the fault signal as its output signal.
The logic value of signal line L16 detected at step A8 is decided to be “0” and the decision level is incremented at step A10.
By virtue of the implication operation performed at step A4, L2=1, L11=1 is implicated at G16 from L16=0.
A logic contradiction is not detected at step A5 and the inferring of logic states is not finished. Control proceeds to step A7 as a result.
Gate G11 is detected as an undetermined gate at step A7. Since a fault signal has been inferred as the output signal of gate G11, the input signal line L3 thereof is selected at step A8.
The logic value of signal line L3 detected at step A8 is decided to be “0” and the decision level is incremented at step A10.
By virtue of the implication operation performed at step A4, L10=1 is implicated at G10 from L3=0.
A logic contradiction is not detected at step A5 and all logic states have been determined. At step A6, therefore, it is determined that the inferring of logic states is finished. Control then proceeds to step A12.
The logic value comparison means 31 extracts a signal line whose state is different from that of the expected value, i.e., extracts a fault propagation path (step A12). As a result, L3, L11, L16 and L23 are extracted as the fault propagation paths.
Furthermore, among the fault propagation paths, L3, L11, L16, L23 are fault propagation paths that have a direct influence upon the fault output terminal when a fault exists on the path. Therefore the extraction means 32 for extracting a line related to a fault outputs these paths to the output unit 5 (step A13).
Since L3 has not been decided to be “1” as a decided line, it is determined at step A14 that processing is not completed and, hence, control proceeds to step A15.
The state that prevailed immediately prior to the decision on L3 is restored by the backtrack means 25. Accordingly, the decision level becomes 1 and the signal lines for which logic values have been decided become L22=1, L23=1, L16=0, L2=1, L11=1 (step A15).
Now a decision to the effect that L3=1 holds is rendered and the decision level becomes dlevel=2 (step A16).
Next, the logic value of the signal line in the logic circuit is found by the implication means 24 at step A4. By virtue of the implication operation at G16, L6=0 is implicated and the logic values of all signals lines are found.
A contradiction is not detected at step A5 and the inferring of logic states ends. Control then proceeds to step A12.
A comparison with expected values is made by the logic value comparison means 31 at step A12, whereby L6, L11, L16 and L23 are extracted as the fault propagation paths.
Since there is a possibility that all of these paths will propagate a fault state to the fault output terminal L23, these paths are output to the output unit 5 (step A13).
By repeating the foregoing processing, all logic states that satisfy L22=1, L23=1 can be found.
FIG. 18 illustrates the above processing in the form of a tree structure. Decisions are rendered for signal lines at two locations, three logic states are found and a fault propagation path corresponding to each state is obtained. The decision level (dlevel) corresponds to the depth of the tree structure, as depicted in FIG. 18.
The conventional system for extracting fault propagation paths finds all fault propagations by repeating logical decisions and implications. However, the circuit is large in scale and, depending upon the faulty locations or input pattern, the number of necessary logical decisions changes significantly. In some cases it is necessary to execute processing of a long period of time ascribable to a large number of decisions.
Although it is possible to suspend processing in mid-course in order that the time needed for inference processing will fall within a practical processing time, there are instances where inference processing will not reach an actual faulty location. In such cases there is the possibility that an actual fault will not be included in a list of fault candidates created on the basis of the fault propagation paths that have been found. The result is a decline in inference precision.
Accordingly, a first problem that arises in the prior art is that there is too much processing for inferring fault propagation paths and the possibility that processing time will become too long. The reason for this is that there are too many logical decisions to be rendered.
A second problem is that the precision with which fault propagation paths are inferred declines if processing is suspended in mid-course. The reason for this is that inference processing will not reach the actual faulty location if processing is suspended, as a consequence of which the fault propagation paths will not include the actual fault.